package com.df.seach;

/**
 * @author dongfang
 * <p>
 * 二分查找，这半查找
 */
public class BinarySearch {
    public static void main(String[] args) {
        System.out.println("hello");

        int[] array = new int[100];

        for (int i = 0; i < 100; i++) {
            array[i] = i << 1;
        }

//        System.out.println("== " + search(8, array, 0, 99));
//        System.out.println("== " + search(9, array, 1, 99));
//        System.out.println("== " + search(98, array, 2, 99));
//        System.out.println("== " + search(198, array, 3, 99));
//        System.out.println("== " + search(298, array, 4, 99));
//        System.out.println("== " + search(398, array, 5, 99));
//        System.out.println("== " + search(98, array, 6, 99));
//        System.out.println("== " + search(98, array, 7, 99));
//        System.out.println("== " + search(98, array, 8, 99));
//        System.out.println("== " + search(11, array, 9, 99));
//        System.out.println("== " + search(11, array, 10, 99));
//        System.out.println("== " + search(11, array, 11, 99));
//        System.out.println("== " + search(11, array, 12, 99));
//
        System.out.println("== " + search(8, array));
        System.out.println("== " + search(9, array));
        System.out.println("== " + search(98, array));
        System.out.println("== " + search(99, array));
        System.out.println("== " + search(28, array));
        System.out.println("== " + search(398, array));
        System.out.println("== " + search(12, array));

//        System.out.println("== " + binarySearch(array, 8));
//        System.out.println("== " + binarySearch(array, 9));
//        System.out.println("== " + binarySearch(array, 98));
//        System.out.println("== " + binarySearch(array, 99));
//        System.out.println("== " + binarySearch(array, 298));
//        System.out.println("== " + binarySearch(array, 398));
//        System.out.println("== " + binarySearch(array, 11));

//        System.out.println("-- " + (~-101));

    }


    static int search(final int value, final int[] array, final int start, final int end) {
        System.out.println(value + " --- s[" + start + "],e[" + end + "]");

        if (value == array[start]) {
            return start;
        }
        if (value == array[end]) {
            return end;
        }

        if ((end - start) < 2 || value < array[start] || value > array[end]) {
            return -1;
        }
        int mid = (start + end) / 2;
        if (value < array[mid]) {
            return search(value, array, start, mid);
        } else {
            return search(value, array, mid, end);
        }

    }


    static int search(final int value, final int[] array) {

        int start = 0, end = array.length - 1;

        int mid = (start + end) >>> 1;

        while (start <= end) {

            System.out.println(value + " --- s[" + start + "],e[" + end + "],m[" + mid + "]");
            if (value == array[start]) {
                return start;
            } else if (value == array[end]) {
                return end;
            } else if (value < array[mid]) {
                end = mid - 1;
            } else if (value > array[mid]) {
                start = mid + 1;
            } else {
                return mid;
            }

            mid = (start + end) >>> 1;
        }

        return -1;
    }


    // This is Arrays.binarySearch(), but doesn't do any argument validation.
    static int binarySearch(int[] array, int value) {
        int lo = 0;
        int hi = array.length - 1;

        while (lo <= hi) {
            final int mid = (lo + hi) >>> 1;
            final int midVal = array[mid];

            if (midVal < value) {
                lo = mid + 1;
            } else if (midVal > value) {
                hi = mid - 1;
            } else {
                return mid;  // value found
            }
        }
        return ~lo;  // value not present
    }

}